Wildcard matching [Greedy]

Time: O(MN); Space: O(1); hard*

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ’*’.

  • ‘?’ Matches any single character.

  • ’*’ Matches any sequence of characters (including the empty sequence).

  • The matching should cover the entire input string (not partial).

Notes:

  • s could be empty and contains only lowercase letters a-z.

  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input: s = “aa”, p = “a”

Output: False

Explanation:

  • “a” does not match the entire string “aa”.

Example 2:

Input: s = “aa”, p = “*”

Output: True

Explanation:

  • ’*’ matches any sequence.

Example 3:

Input: s = “cb”, p = “?a”

Output: False

Explanation:

  • ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.

Example 4:

Input: s = “adceb”, p = “*a*b”

Output: True

Explanation:

  • The first ‘*’ matches the empty sequence, while the second ’*’ matches the substring “dce”.

Example 5:

Input: s = “acdcb”, p = “a*c?b”

Output: False

1. Iterative solution with Greedy

[12]:

class Solution1(object):
    """
    Time: O(M+N)~O(M*N)
    Space: O(1)
    """
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        count = 0  # used for complexity check
        p_ptr, s_ptr, last_s_ptr, last_p_ptr = 0, 0, -1, -1
        while s_ptr < len(s):
            if p_ptr < len(p) and (s[s_ptr] == p[p_ptr] or p[p_ptr] == '?'):
                s_ptr += 1
                p_ptr += 1
            elif p_ptr < len(p) and p[p_ptr] == '*':
                p_ptr += 1
                last_s_ptr = s_ptr
                last_p_ptr = p_ptr
            elif last_p_ptr != -1:
                last_s_ptr += 1
                s_ptr = last_s_ptr
                p_ptr = last_p_ptr
            else:
                assert(count <= (len(p)+1) * (len(s)+1))
                return False
            count += 1  # used for complexity check

        while p_ptr < len(p) and p[p_ptr] == '*':
            p_ptr += 1
            count += 1  # used for complexity check

        assert(count <= (len(p)+1) * (len(s)+1))

        return p_ptr == len(p)

[13]:

sol = Solution1()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False
s = "aa"
p = "*"
assert sol.isMatch(s, p) == True
s = "cb"
p = "?a"
assert sol.isMatch(s, p) == False
s = "adceb"
p = "*a*b"
assert sol.isMatch(s, p) == True
s = "acdcb"
p = "a*c?b"
assert sol.isMatch(s, p) == False

2. Dynamic Programming with rolling window

[14]:

class Solution2(object):
    def isMatch(self, s, p):
        k = 2
        result = [[False for j in range(len(p) + 1)] for i in range(k)]

        result[0][0] = True
        for i in range(1, len(p) + 1):
            if p[i-1] == '*':
                result[0][i] = result[0][i-1]
        for i in range(1,len(s) + 1):
            result[i % k][0] = False
            for j in range(1, len(p) + 1):
                if p[j-1] != '*':
                    result[i % k][j] = result[(i-1) % k][j-1] and (s[i-1] == p[j-1] or p[j-1] == '?')
                else:
                    result[i % k][j] = result[i % k][j-1] or result[(i-1) % k][j]

        return result[len(s) % k][len(p)]

[15]:

sol = Solution2()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False
s = "aa"
p = "*"
assert sol.isMatch(s, p) == True
s = "cb"
p = "?a"
assert sol.isMatch(s, p) == False
s = "adceb"
p = "*a*b"
assert sol.isMatch(s, p) == True
s = "acdcb"
p = "a*c?b"
assert sol.isMatch(s, p) == False

3. Dynamic Programming

[16]:

class Solution3(object):
    def isMatch(self, s, p):
        result = [[False for j in range(len(p) + 1)] for i in range(len(s) + 1)]

        result[0][0] = True
        for i in range(1, len(p) + 1):
            if p[i-1] == '*':
                result[0][i] = result[0][i-1]
        for i in range(1,len(s) + 1):
            result[i][0] = False
            for j in range(1, len(p) + 1):
                if p[j-1] != '*':
                    result[i][j] = result[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '?')
                else:
                    result[i][j] = result[i][j-1] or result[i-1][j]

        return result[len(s)][len(p)]

[17]:

sol = Solution3()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False
s = "aa"
p = "*"
assert sol.isMatch(s, p) == True
s = "cb"
p = "?a"
assert sol.isMatch(s, p) == False
s = "adceb"
p = "*a*b"
assert sol.isMatch(s, p) == True
s = "acdcb"
p = "a*c?b"
assert sol.isMatch(s, p) == False

4. Recursive, slowest, TLE

[18]:

class Solution4(object):
    def isMatch(self, s, p):
        if not p or not s:
            return not s and not p

        if p[0] != '*':
            if p[0] == s[0] or p[0] == '?':
                return self.isMatch(s[1:], p[1:])
            else:
                return False
        else:
            while len(s) > 0:
                if self.isMatch(s, p[1:]):
                    return True
                s = s[1:]
            return self.isMatch(s, p[1:])

[19]:

sol = Solution4()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False
s = "aa"
p = "*"
assert sol.isMatch(s, p) == True
s = "cb"
p = "?a"
assert sol.isMatch(s, p) == False
s = "adceb"
p = "*a*b"
assert sol.isMatch(s, p) == True
s = "acdcb"
p = "a*c?b"
assert sol.isMatch(s, p) == False